class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> ret;
        map<string, int> countMap;
        for(auto& str : words)
        {
            countMap[str]++;
        }
        // 上面的步骤把words插入map后，就是默认按单词的首字母按从小到大排序好的
        // e.g:["love","i","leetcode","i","love","coding"]
        // 排完是：
        // coding 1
        // i 2
        // leetcode 1
        // love 2

        // 后面如果使用multimap默认不给仿函数的话是升序
        // 所以如果次数相同的话，i一定是在love前面
        // 此时如果我们用反向迭代器去从后往前遍历是，先拿到的是love，再是i，不符合题目要求

        // 解决办法：
        // 使用multimap时给定降序的仿函数
        // 如果次数相同的话，i也一定是在love前面
        // 排完是：
        // 2 i
        // 2 love
        // 1 coding
        // 1 leetcode

        // 这样也就不用反向迭代器了，要前几个高频的就拿前几个，且次数相同的也按从小到大排序了

        // 指定降序
        multimap<int, string, greater<int>> sortMap;
        for(auto& e : countMap)
        {
            sortMap.insert(make_pair(e.second, e.first));
        }
        
        auto it = sortMap.begin();
        while(it != sortMap.end())
        {
            if(k == 0)
                break;
            
            ret.push_back((*it).second);
            it++;
            k--;
        }

        return ret;
    }
};